package LearnDataStructure.a_线性结构.例题;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-04 19:16
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 */

import java.util.Stack;

/**
 * 请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
 给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
 测试样例：
 [1,2,3,4,5]
 返回：[5,4,3,2,1]
 */
public class k_升序排序栈且空间利用唯一的帮助站 {
    public static void main(String[] args) {
        k_升序排序栈且空间利用唯一的帮助站 test = new k_升序排序栈且空间利用唯一的帮助站();
        int[] arr = {5, 2, 3, 4, 9};
        test.useStackSort(arr);
    }

    public void useStackSort(int[] arr) {
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = arr.length - 1; i >= 0; i--) {
            stack.push(arr[i]);
        }
        Stack<Integer> stackSort = stackSort(stack);
        while (!stackSort.empty()) {
            System.out.println(stackSort.pop());
        }
    }

    public Stack<Integer> stackSort(Stack<Integer> source) {
        Stack<Integer> helper = new Stack<Integer>();
        while (!source.empty()) {
            int value = source.pop();//左栈的栈顶元素，即“盖子”
            if (helper.empty()) {
                helper.push(value);//右栈的初始化
            } else {
                int helperTop = helper.peek();//右栈的主要操作逻辑
                if (value >= helperTop) {//盖子大于右栈栈顶元素
                    helper.push(value);//直接存右栈
                } else {
                    while (!helper.empty() && value < helper.peek()) {//不大于，那就一直弹右栈，直到找到符合条件的元素或者弹空右栈
                        source.push(helper.pop());
                    }
                    helper.push(value);
                }
            }
        }
        return helper;
    }
}
